import java.util.LinkedList;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: LENOVO
 * Date: 2024-08-07
 * Time: 10:09
 */
public class Test {
     public static class ListNode {
          int val;
          ListNode next;
          ListNode(int x) {
              val = x;
          }
     }
    private static int kthToLast(ListNode head, int k) {
         ListNode fast = head;
         ListNode slow = head;
         if(head == null){
             return -1;
         }
         while(k - 1 != 0){
             fast = fast.next;
             if(fast == null){
                 return -1;
             }
             k--;
         }
         while(fast.next != null){
             slow = slow.next;
             fast = fast.next;
         }
         return slow.val;
    }
    public static ListNode reverseList(ListNode head) {
         if(head == null){
             return head;
         }
        ListNode cur = head.next;
         head.next = null;
        while(cur != null){
            ListNode curN = cur.next;
            cur.next = head;
            head = cur;
            cur = curN;
        }
        return head;
    }
    public static ListNode removeElements(ListNode head, int val) {
        if(head == null){
            return head;
        }
        ListNode cur = head;
        while(cur.next != null){
            if(cur.next.val == val){
                cur.next = cur.next.next;
                continue;
            }
            cur = cur.next;
        }
        if(head.val == val){
            head = head.next;
        }
        return head;
    }

    public static ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        return slow;
    }





    public static boolean chkPalindrome(ListNode A) {
         //拿到了头指针之后 ，我们到该链表的中间位置去，在中间位置正好是slow的位置
        //要判断是否是回文链表，我们只需要把该链表一分为二，把后边的按从后往前再去重新连接，再分别从左右两端
        //向中间遍历，判断每个节点除的值相等不相等
        ListNode slow = A;
        ListNode fast = A;
        //  这个对应的是偶数个     这个对应的是奇数个，这个到达了末尾，结束条件是fast.next=null
        //这个最后是fast=null
        //在这个循环里面，我们的最终目的是摆好slow和fast的位置，所以我们要看的是循环结束之后二者的最后位置
        while(fast != null && fast.next != null){ // fast!=null放前面是防止空指针异常
            fast = fast.next.next;
            slow = slow.next;
        }//到这里  slow就到了中间位置
        ListNode cur = slow.next;
        ListNode curN = cur;
        while(cur != null){ // 最后一个节点能够进来，因为最后一个节点本身非空
            curN = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curN;
        }
        //现在最左边是head()[本题中叫做A],最右边是我们的slow(不用fast是因为在偶数情况下fast已经出去了是null了)
        //循环条件理应是左.next=右
        while(A != slow){
            if(A.val != slow.val){
                return false;
            }
            if(A.next == slow){
                return true;
            }
            A = A.next;
            slow = slow.next;
        }
        return true;
     }





    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //list1是链表1的头
         ListNode newHeadNode = new ListNode(-1);//想搞一个头节点，这里用来存储我们第一个节点的指针
         ListNode tmp = newHeadNode; //搞一个指向头结点的指针来操作头节点，同时还能往后走,用tmp来标记已确认的节点，操作已经确认好的节点的next来连接下一个节点
         while(list1 != null & list2 != null){
             if(list1.val < list2.val){
                tmp.next = list1;
                list1 = list1.next;
                tmp =tmp.next;
             }else{
                 tmp.next = list2;
                 list2 = list2.next;
                 tmp = tmp.next;
             }
         }
         if(list1 != null){
             tmp.next = list1;
         }
         if(list2 != null){
             tmp.next =list2;
         }
         return newHeadNode.next;
    }


    public static ListNode partition(ListNode pHead, int x) {
         ListNode bs= null;//小于的那一块的头
         ListNode be = null;//尾
         ListNode as = null;
         ListNode ae = null;
         ListNode cur = pHead;
         while(cur != null){
             if(cur.val < x){
                 if(be == null){
                     bs = be = cur;
                 }else {
                     be.next = cur;
                     be = cur;
                 }
             }else{
                 if(ae == null){
                     as = ae = cur;
                 }else {
                     ae.next = cur;
                     ae = cur;
                 }
             }
             cur = cur.next;
         }
         if(bs == null){
             return as;
         }
         if(as != null){
             ae.next = null;
         }
         be.next = as;
         return bs;
    }





    public static void main(String[] args) {
        ListNode node0 = new ListNode(0);
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
/*        ListNode node3 = new ListNode(1);
        ListNode node4 = new ListNode(0);*/
        ListNode node3 = new ListNode(2);
        ListNode node4 = new ListNode(1);
        ListNode node5 = new ListNode(0);
        node0.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        ListNode head = node0;
        ListNode node00 = new ListNode(0);
        ListNode node11 = new ListNode(1);
        ListNode node22 = new ListNode(2);
        node00.next = node11;
        node11.next = node22;
        ListNode head00 = node0;
/*        int ret =  kthToLast(head,3);
        System.out.println(ret);
        *//*ListNode head0 = reverseList(head);*//*
        ListNode head0 = removeElements(head,1);
        ListNode cur = head0;*/
/*        ListNode retNode = middleNode(head);*/
        System.out.println(chkPalindrome(head));
        /*        System.out.println(retNode.val);*/
/*        for (int i = 0; i < 4; i++) {
            System.out.println(cur.val);
            cur = cur.next;
        }*/
/*        ListNode retHead = mergeTwoLists(head,head00);*/
        partition(head, 1);

        }
}
